package com.sicheng.lc.lc笔试.字节篇;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/6 18:23
 */
public class 背包 {
    public static void main(String[] args) {
        /*
第三题：背包
给定n个任务需要花费的时间和产生的价值，最多只能花费m个时间，且只能完成两个任务，若不足2个任务，则返回0.
2 < n <= 1e6, 0 <= m <= 1e6
输入：
4 6
1 8
2 1
4 3
6 4
输出
11
   *
   *
   * */
        // write your code here
        Scanner scanner = new Scanner(System.in);
        //n个任务
        int n = scanner.nextInt();
        //m:总时间
        int m = scanner.nextInt();

        //每个任务所需的时间
        int[] w = new int[n];
        //每个任务的价值
        int[] v = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }

        long[][] dp = new long[3][m + 1];
//        boolean[] used = new boolean[n];
        int[] stats = new int[m + 1];
        //第k行
        for (int k = 1; k < 3; k++) {
            //第i个物品
            for (int i = 0; i < n; i++) {
                //当前容量为j
                for (int j = m; j >= w[i]; j--) {
                    if (k == 1) {
                        if (v[i] > dp[k][j]) {
                            //放状态stats
                            stats[j] = 1 << i;
                            dp[k][j] = v[i];
                        }
                    } else {
                        if (dp[k - 1][j - w[i]] > 0 && (stats[j - w[i]] >> i & 1) != 1) {
                            dp[k][j] = Math.max(dp[k][j], dp[k - 1][j - w[i]] + v[i]);
                        }
                    }
                }
            }
        }
        System.out.println(dp[2][m]);
    }
}
